package 系统复习.链表;

import datastructure.ListNode;

/**
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
 */

public class L24 {

    public static ListNode swapPairs(ListNode head) {

        // 递归算法
        // 这个整体思路是 吧 swapPairs(newHead.next)看做一个节点 也就是一个指针 就变为三个节点的转换 ListNode newHead = head.next; head.next = swapPairs(newHead.next); newHead.next = head;
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // swapPairs(ListNode head) 的意义就是两两翻转链表中的节点+返回翻转后的新的头结点
        // 我们知道翻转后新的头结点必然是第二个节点
        // 举例子:1->2->3->4 翻转后:2->1->4->3
        ListNode next = head.next;
        // 此时newNode:4->3
        ListNode newNode = swapPairs(next.next);
        // 而前面的还粘连着:1->2->(3)  4->3
        // 此时再让1->4 此时链表为:2->(3) 1->4->3
        next.next = head;
        // 再将2指向1即可 此时链表为:2->1->4->3 已经完成翻转
        head.next = newNode;

        return next;


//        ListNode virtual = new ListNode();
//        virtual.next = head;
//        ListNode cur = virtual;
//        ListNode temp;
//        ListNode firstNode;
//        ListNode secondNode;
//
//        while (cur.next != null && cur.next.next != null) {
//            temp = cur.next.next.next;
//            firstNode = cur.next;
//            secondNode = cur.next.next;
//            cur.next = secondNode;
//            secondNode.next = firstNode;
//            firstNode.next = temp;
//            cur = firstNode;
//        }
//
//        return virtual.next;
    }

    public static void main(String[] args) {

        ListNode listNode = swapPairs(ListNode.buildList(new int[]{1, 2, 3, 4}));
        ListNode.printListNode(listNode);


    }

}
